/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */



//1. 朴素做法：遍历长度，得出中间节点位置
// class Solution 
// {
// public:
//     ListNode* middleNode(ListNode* head) 
//     {
//         if(head==nullptr)
//             return head;
//         ListNode* cur=head;
//         int count=0;
//         while(cur)
//         {
//             cur=cur->next;
//             count++;
//         }
//         int pos=count/2;
//         while(pos--)
//         {
//             head=head->next;
//         }
//         return head;
//     }
// };


//2. 快慢双指针
class Solution 
{
public:
    ListNode* middleNode(ListNode* head) 
    {
       ListNode* slow=head,*fast=head;
       while(fast&&fast->next)
       {
            fast=fast->next->next;
            slow=slow->next;
       }
       return slow;
    }
};